{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"../../img/ods_stickers.jpg\">\n",
    "## Открытый курс по машинному обучению. Сессия № 2\n",
    "</center>\n",
    "Автор материала: программист-исследователь Mail.ru Group, старший преподаватель Факультета Компьютерных Наук ВШЭ Юрий Кашницкий. Материал распространяется на условиях лицензии [Creative Commons CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/). Можно использовать в любых целях (редактировать, поправлять и брать за основу), кроме коммерческих, но с обязательным упоминанием автора материала."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <center>Тема 7. Обучение без учителя\n",
    "## <center>Часть 2. Метрики качества кластеризации"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Задача оценки качества кластеризации является более сложной по сравнению с оценкой качества классификации. Во-первых, такие оценки не должны зависеть от самих значений меток, а только от самого разбиения выборки. Во-вторых, не всегда известны истинные метки объектов, поэтому также нужны оценки, позволяющие оценить качество кластеризации, используя только неразмеченную выборку.\n",
    "\n",
    "Выделяют **внешние** и **внутренние** метрики качества. Внешние используют информацию об истинном разбиении на кластеры, в то время как внутренние метрики не используют никакой внешней информации и оценивают качество кластеризации, основываясь только на наборе данных. Оптимальное число кластеров обычно определяют с использованием внутренних метрик.\n",
    "\n",
    "Все указанные ниже метрики реализованы в `sklearn.metrics`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Adjusted Rand Index (ARI)\n",
    "\n",
    "Предполагается, что известны истинные метки объектов. Данная мера не зависит от самих значений меток, а только от разбиения выборки на кластеры. Пусть $N$ – число объектов в выборке. Обозначим через $a$ число пар объектов, имеющих одинаковые метки и находящихся в одном кластере, через $b$ – число пар объектов, имеющих различные метки и находящихся в разных кластерах. Тогда Rand Index это $$\\text{RI} = \\frac{2(a + b)}{N(N-1)}.$$ То есть это доля объектов, для которых эти разбиения (исходное и полученное в результате кластеризации) \"согласованы\". Rand Index (RI) выражает схожесть двух разных кластеризаций одной и той же выборки. Чтобы этот индекс давал значения близкие к нулю для случайных кластеризаций при любом $N$ и числе кластеров, необходимо нормировать его. Так определяется Adjusted Rand Index: $$\\text{ARI} = \\frac{\\text{RI} - E[\\text{RI}]}{\\max(\\text{RI}) - E[\\text{RI}]}.$$\n",
    "\n",
    "Эта мера симметрична, не зависит от значений и перестановок меток. Таким образом, данный индекс является мерой расстояния между различными разбиениями выборки. $\\text{ARI}$ принимает значения в диапазоне $[-1, 1]$. Значения, близкие к нулю соответствуют случайным разбиениям, а положительные значения говорят о том, что два разбиения схожи (совпадают при $\\text{ARI} = 1$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Adjusted Mutual Information (AMI)\n",
    "\n",
    "Данная мера очень похожа на $\\text{ARI}$. Она также симетрична, не зависит от значений и перестановок меток. Определяется с использованием функции [энтропии](https://en.wikipedia.org/wiki/Entropy_(information_theory), интерпретируя разбиения выборки, как дискретные распределения (вероятность отнесения к кластеру равна доле объектов в нём). Индекс $MI$ определяется как  [взаимная информация](https://en.wikipedia.org/wiki/Mutual_information) для двух распределений, соответствующих разбиениям выборки на кластеры. Интуитивно, взаимная информация измеряет долю информации, общей для обоих разбиений: насколько информация об одном из них уменьшает неопределенность относительно другого.\n",
    "\n",
    "Аналогично $\\text{ARI}$ определяется индекс $\\text{AMI}$, позволяющий избавиться от роста индекса $MI$ с увеличением числа классов. Он принимает значения в диапазоне $[0, 1]$. Значения, близкие к нулю, говорят о независимости разбиений, а близкие к единице – об их схожести (совпадении при $\\text{AMI} = 1$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Homogeneity, completeness, V-measure\n",
    "\n",
    "Формально данные меры также определяются с использованием функций энтропии и условной энтропии, рассматривая разбиения выборки как дискретные распределения:$$h = 1 - \\frac{H(C\\mid K)}{H(C)}, c = 1 - \\frac{H(K\\mid C)}{H(K)},$$\n",
    "здесь $K$ – результат кластеризации, $C$ – истинное разбиение выборки на классы. Таким образом, $h$ измеряет, насколько каждый кластер состоит из объектов одного класса, а $c$ – насколько объекты одного класса относятся к одному кластеру. Эти меры не являются симметричными. Обе величины принимают значения в диапазоне $[0, 1]$, и большие значения соответствуют более точной кластеризации. Эти меры не являются нормализованными, как $\\text{ARI}$ или $\\text{AMI}$, и поэтому зависят от числа кластеров. Случайная кластеризация не будет давать нулевые показатели при большом числе классов и малом числе объектов. В этих случаях предпочтительнее использовать $\\text{ARI}$. Однако при числе объектов более 1000 и числе кластеров менее 10 данная проблема не так явно выражена и может быть проигнорирована.\n",
    "\n",
    "Для учёта обеих величин $h$ и $c$ одновременно вводится $V$-мера как их среднее гармоническое:\n",
    "$$v = 2\\frac{hc}{h+c}.$$\n",
    "Она является симметричной и показывает, насколько две кластеризации схожи между собой.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Силуэт\n",
    "\n",
    "В отличие от описанных выше метрик, данный коэффициент не предполагает знания истинных меток объектов и позволяет оценить качество кластеризации, используя только саму (неразмеченную) выборку и результат кластеризации. Сначала силуэт определяется отдельно для каждого объекта. Обозначим через $a$ – среднее расстояние от данного объекта до объектов из того же кластера, через $b$ – среднее расстояние от данного объекта до объектов из ближайшего кластера (отличного от того, в котором лежит сам объект). Тогда силуэтом данного объекта называется величина: $$s = \\frac{b - a}{\\max(a, b)}.$$\n",
    "Силуэтом выборки называется средняя величина силуэта объектов данной выборки. Таким образом, силуэт показывает, на сколько среднее расстояние до объектов своего кластера отличается от среднего расстояния до объектов других кластеров. Данная величина лежит в диапазоне $[-1, 1]$. Значения, близкие к -1, соответствуют плохим (разрозненным) кластеризациям, значения, близкие к нулю, говорят о том, что кластеры пересекаются и накладываются друг на друга, значения, близкие к 1, соответствуют \"плотным\", четко выделенным кластерам. Таким образом, чем больше силуэт, тем более четко выделены кластеры, и они представляют собой компактные, плотно сгруппированные облака точек.\n",
    "\n",
    "С помощью силуэта можно выбирать оптимальное число кластеров $k$ (если оно заранее не известно) – выбирается число кластеров, максимизирующее значение силуэта. В отличие от предыдущих метрик, силуэт зависит от формы кластеров и достигает больших значений на более выпуклых кластерах, получаемых с помощью алгоритмов, основанных на восстановлении плотности распределения."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Полезные ссылки\n",
    "\n",
    "- [Внешние и внутренние метрики качества](https://en.wikipedia.org/wiki/Cluster_analysis#Evaluation_and_assessment)\n",
    "- <a href=\"https://en.wikipedia.org/wiki/Silhouette_(clustering)\">Силуэт</a>\n",
    "- [Информация в sklearn](http://scikit-learn.org/stable/modules/clustering.html#clustering-performance-evaluation)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  },
  "name": "lesson8_part5_clustering_metrics.ipynb"
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
